package com.bn.test1;
import java.util.*;


public class LevelOrderTraversal {
	
	public static void main(String [] args) {
		Node root = TreeUtil.createSampleTree(); 

		/*
		 *              a
		 *         b              c
		 *     d      e       f       g
		 *   h   i          j  k
		 *   
		 *   print: a c b d e f g k j i h
		 */
		//levelOrderTraversal_y(root);
		zigzag_levelOrderTraversal(root);
	}
	
	public static void levelOrderTraversal_y(Node root) {
	    Queue<Node> q = new LinkedList<Node>();
	    q.add(root);
	    while (!q.isEmpty()) {
	        Node n = q.poll();
	        System.out.print(n.val + " ");
	        addChildren(q, n);
	    }
	}
	
	/*
	 *              a
	 *         b              c
	 *     d      e       f       g
	 *   h   i          j  k
	 *   
	 *   print: a c b d e f g k j i h
	 */
	public static void zigzag_levelOrderTraversal(Node root) {
		Stack<Node> s1 = new Stack<Node>();
		Stack<Node> s2 = new Stack<Node>();
		int level = 1;
	    s1.add(root);
	    while (!s1.isEmpty() || !s2.isEmpty()) {
	    	if(!s1.isEmpty()){
	    		while(!s1.isEmpty()){
	    			if (level % 2 != 0){
	    				Node n = s1.pop();
	    				System.out.print(n.val + " ");
	    				addChildren(s2, n);
	    			}
	    			else{
	    				Node n = s1.pop();
	    				System.out.print(n.val + " ");
	    				addChildrenRev(s2, n);
	    			}
	    		}
	    		++level;
    		}
	    	else{
	    		while(!s2.isEmpty()){
	    			if (level % 2 != 0){
	    				Node n = s2.pop();
	    				System.out.print(n.val + " ");
	    				addChildren(s1, n);
	    			}
	    			else{
	    				Node n = s2.pop();
	    				System.out.print(n.val + " ");
	    				addChildrenRev(s1, n);
	    			}
	    		}
	    		++level;
	    	}
	    	}
	    }

	private static void addChildrenRev(Stack<Node> s, Node n) {
		if (n.right != null) 
		    s.add(n.right);
		
		if (n.left != null) 
		    s.add(n.left);
	}
	
	private static void addChildren(Stack<Node> s, Node n) {
		if (n.left != null) 
		    s.add(n.left);
		
		if (n.right != null) 
		    s.add(n.right);
	}

	private static void addChildren(Queue<Node> q, Node n) {
		if (n.left != null) 
		    q.add(n.left);
		
		if (n.right != null) 
		    q.add(n.right);
	}
}


